1. Field of the Invention
The present invention relates to data communications networks and, in particular, to an elasticity buffer that provides temporary character storage in a network station to compensate for differences in frequency between the station's local transmit clock and a data sampling clock recovered from the incoming data stream.
2. Discussion of the Prior Art
Communication between stations in a communications network occurs through the transmission of a series, or "frame", of information characters, with adjacent frames being separated by explicit or implicit start-stop code patterns. The use of a unique start pattern ("start delimiter") and a unique stop pattern ("end delimiter") allows the receiving station to identify the exact beginning and the exact end of each frame.
When information frames are being transmitted from one station in the network to another, the data sampling timing of the receiving station must be the same as or very close to the transmit timing of the transmitting station in order to achieve reliable information frame propagation. If there is a timing difference between the transmitting station and the receiving station, then data sampling at the receiver station will drift, causing eventual data sampling error at the limits of the information frames and, hence, system malfunctioning.
In some local area networks, and in almost all "asynchronous" communications links, each station samples incoming data received from an upstream transmitting station based upon a "receive" clock which is recovered from the incoming data signal. The receiving station, in turn, relies upon an indpendent "local" clock to retransmit the recovered data. Network synchronization may be maintained by utilizing an elasticity buffer in each station to provide temporary storage for the recovered data to compensate for phase and frequency differences between the recovered data sampling clock and the local transmit clock.
A particular type of data communications network is defined by the Fiber Distributed Data Interface (FDDI) protocol. The FDDI protocol is an American National Standard (ANS) for data transmission which applies to a 100 Mbits/sec. token ring network that utilizes an optical fiber transmission medium. The FDDI protocol is intended as a high performance interconnection among computers as well as among computers and their associated mass storage subsystems and other peripheral equipment.
Information is transmitted on an FDDI ring in frames that consist of a sequence of 5-bit data characters or "symbols", each symbol representing four data bits. Tokens are used to signify the right to transmit information frames between stations on the network.
Of the thirty-two member FDDI standard symbol set, sixteen are data symbols (each representing four bits of ordinary binary data) and eight are control symbols. The eight control symbols include J (the first symbol of a start delimiter byte JK), K (the second symbol of the start delimiter byte JK), I (Idle), H (Halt), Q (Quiet), T (End Delimiter), S (Set) and R (Reset).
The remaining eight symbols of the FDDI standard symbol set are not used because they violate code run length or DC balance requirements of the protocol.
A continuous stream of control symbol patterns defines a line state. The FDDI protocol defines seven line states:
(1) Idle Line State (ILS), which is a continuous stream of Idle symbols; PA1 (2) Quiet Line State (QLS), which is a continuous stream of Halt Symbols; PA1 (3) Halt Line State (HLS), which is a continuous stream of Halt symbols; PA1 (4) Master Line State (MLS), which is a continuous stream of alternating Halt and Quiet symbols; PA1 (5) Reception of a start delimiter symbol pair JK, indicating ALS; PA1 (6) Noise Line State (NLS); and PA1 (7) Line State Unknown (LSU).
FIG. 1 shows the fields which are used within the FDDI frame and token formats. A preamble field (PA), which consists of a sequence of Idle line-state symbols, precedes every transmission. The Idle symbols provide a maximum frequency signal which is used for receive clock synchronization. The Start Delimiter field (SD) consists of a two symbol start delimiter pair which is uniquely recognizable independent of symbol boundaries.
As stated above, the Start Delimiter byte establishes the boundaries for the information that follows. The Frame Control field (FC) defines the type of frame and its characteristics; it distinguishes synchronous from asynchronous transmission, specifies the length of the address and identifies the type of frame. The Frame Control field uniquely distinguishes a token. The Ending Delimiter field (ED) of a token consists of two end delimiter symbols and completes a token.
The Destination Address (DA) and Source Address (SA) fields contain the destination and source addresses of the transmitted frame. The Destination Address field and the Source Address field are both either two bytes long or six bytes long, as determined by the Frame Control field. The Destination Address may be either an individual address or a group address. The Frame Check Sequence field (FCS), which is four bytes long, contains a cyclic redundancy check using the ANSI standard polynomial. The INFORMATION field, as is the case for all fields covered by the Frame Check Sequence check, consists only of data symbols. The End Delimiter of a frame is one end delimiter symbol (T), which is followed by the Frame Status field (FS) which consists of three control indicator symbols which indicate whether the addressed station has recognized its address, whether the frame has been copied, or whether any station has detected an error in the frame. The "T" followed by three control indicators represents the minimum end of frame sequence (EFS) required by the FDDI protocol for a non-token frame. The protocol allows for additional pairs of control symbols in the EFS or an additional odd number of control symbols followed by one last "T" symbol. All conforming implementations must be able to process these extended end delimiters without truncating them. The end delimiter "T" and the two control symbols "R" and "S" are uniquely encoded and distinguishable from either normal data or Idle symbols.
FIG. 2 shows the component entities included in a station that is in compliance with the FDDI protocol. The identified components include a Station Management function (SMT) which is a part of network management that resides in each station on the network to control the overall action of the station to ensure proper operation as a member of the ring. A Physical Layer Medium Dependent (PMD) function provides the fiber-optic links between adjacent stations on the ring. A Physical function (PHY) provides the encoding, decoding, clocking and synchronization functions. A Media Access Control function (MAC) controls access to the transmission medium, transmitting frames to and receiving frames from the MACs of other stations.
The PHY simultaneously receives and transmits information. The PHY's transmit logic accepts symbols from the MAC, converts these symbols to 5-bit code groups and transmits the encoded serial stream on the medium. The PHY's receive logic receives the encoded serial stream from the medium, establishes symbol boundaries based on the recognition of a start delimiter symbol pair and forwards decoded symbols to its associated MAC.
Additional information regarding the FDDI protocol is presented by Floyd E. Ross, "FDDI--an Overview", Digest of Papers, Computer Soc. Intl. Conf., Compcon '87, pp. 434-444, which is hereby incorporated by reference to provide additional background information relating to the present invention.
To reduce jitter accumulation in any signal transmitted on a ring network, as stated above, each station on the FDDI ring must transmit with its own local clock ("jitter" is defined as the short term variation of the transition edges of the digital signal from their ideal positions). According to the FDDI protocol, this local clock is allowed to have a maximum frequency variation of only .+-.50 PPM from the transmit clock frequency of other stations in the network at a transmission rate of 125 Mbits/sec. Because the transmitted data are encoded according to a 4B/5B scheme, that is, 4 bits of data are encoded to create a 5-bit symbol, the 125 Mbit/sec. FDDI transmission rate translates to a 100 Mbit/sec. data rate.
To accommodate the maximum allowable .+-.50 PPM frequency variation between stations on an FDDI network, the FDDI protocol requires that an elasticity buffer providing at least plus/minus 4.5 bits of elasticity be incorporated in each station. The recovered receive clock writes data into the elasticity buffer and the local transmit clock reads the data from the elasticity buffer in the same order as written for retransmission on the ring.
The design of a conventional elasticity buffer is relatively straightforward. Basically, an elasticity buffer is a cyclic buffer queue, that is, a series of sequentially accessed storage registers wherein access for a particular operation, i.e. write or read, returns or "wraps around" to the first register in the series after the last register in the series has been accessed for that operation. Write pointer logic, typically an incrementing counter, holds the address of the storage register currently accessed for a write operation. Similarly, read pointer logic holds the address of the storage register currently being accessed for a read operation.
The elasticity buffer's write pointer starts writing receive symbols into the storage registers of the elasticity buffer upon identifying a start delimiter and stops writing symbols after an end delimiter has been written. Similarly, the elasticity buffer's read pointer starts reading symbols from the storage registers upon receiving a read-start signal and stops reading symbols after reading an end delimiter.
A major limitation of the conventional cyclic queue elasticity buffer design is its requirement that a time gap of at least one control symbol character or more of a certain pattern exist between sequential data frames. That is, since the conventional elasticity buffer depends on the appearance of at least one Idle symbol pair to function correctly, a conventional elasticity buffer cannot handle back-to-back information frames with no separation. Also, since there is no predetermined start area for the second and subsequent back-to-back data frames, both the write and the read pointer logic must "remember" their previous positions. In addition, a conventional elasticity buffer cannot function with a continuous stream of line state characters which contains neither a start delimiter nor an end delimiter. Furthermore, a conventional elasticity buffer is not readily testable due to its indeterministic addressing scheme, i.e., a start delimiter symbol pair JK can be written anywhere in the cyclic buffer and therefore, cannot be readily anticipated in a particular storage register.
An elasticity buffer architecture which addresses the limitations of a conventional elasticity buffer design is disclosed in co-pending and commonly assigned U.S. patent application Ser. No. 338,587, which was filed on Apr. 14, 1989 by Gabriel Li and James R. Hamstra (co-inventor of the subject invention) for SYMBOL-WIDE ELASTICITY BUFFER; the co-pending Li et al application is hereby incorporated by reference to provide additional background information regarding the present invention.
The basic storage core of the elasticity buffer disclosed by Li et al is divided into two distinct sections, a START section and a CONTINUATION section. The elasticity buffer's write pointer will not enter the CONTINUATION section, which constitutes a conventional cyclic queue, until the read pointer is directed to the first of the multiple, sequential registers included in the START section. The read pointer must then sequentially read each of the START section registers before entering the CONTINUATION section. Once the write pointer or the read pointer has left the START section, it can only re-enter upon receipt of a start delimiter signal. When the write pointer or read pointer reaches the last register in the multiple register CONTINUATION section, it is automatically routed back to the first register in the CONTINUATION section, unless the R-Flag is set. In this case, the elasticity buffer "stalls", that is, it repeatedly reads the last register in the CONTINUATION section until a "start" or "continue" signal is received.
Thus, the Li et al design provides a number of advantages over conventional elasticity buffers. First, the length of the START section determines the maximum separation of the read pointer and the write pointer. Second, to handle back-to-back information frames without separation, one more buffer is added to the START section and the write pointer issues a start signal to the read pointer one symbol time after writing this register. Third, since the write pointer doesn't need to know the position of the read pointer when starting a new frame, the write pointer control logic is greatly simplified.
While the Li et al elasticity buffer described above provides advantages over conventional elasticity buffer designs, it cannot handle some practical applications. For example, it does not prevent token trashing or accommodate any short back-to-back frames. It requires a long write pointer chain and a long read pointer chain with extra logic to reset the counters against possible alpha particle hit. Since both the write pointer and the read pointer may stop, extra stopping logic is required. Nor does it provide overflow/underflow detection.